package tulingxueyuan117;

import java.util.Arrays;

/**
 * Author: Zhang Dongwei
 * Date: 2022/11/6 14:52
 * 快速升序排序（很重要）
 */
public class p38_堆排序_912 {
    public static void main(String[] args) {
        int[] arr = {86,39,77,23,32,45,58,63,93,4,37,22};
        System.out.println(Arrays.toString(arr));
        int[] res = heapSort(arr);
        System.out.println("=========================");
        System.out.println(Arrays.toString(res));
    }
    private static int len;
    public static int[] heapSort(int[] nums) {
        len = nums.length;
        if(len<=1) return nums;
        buildMaxHeap(nums);
        while (len>0){
            swap(nums, 0, len-1);
            len --;
            adjustHeap(nums, 0);
        }
        return nums;
    }
    public static void buildMaxHeap(int[] array){
        for(int i = (len/2-1); i>=0; i--){
            adjustHeap(array, i);
        }
    }
    public static void adjustHeap(int[] array, int i){
        int maxIndex = i;
        int left = 2*i+1;
        int right = 2*(i+1);
        if(left<len && array[left] > array[maxIndex])
            maxIndex = left;
        if(right<len && array[right]>array[maxIndex] && array[right]>array[left])
            maxIndex = right;
        if(maxIndex != i){
            swap(array, maxIndex, i);
            adjustHeap(array, maxIndex);
        }
    }
    public static void swap(int[] array, int i, int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}
